<?php
/**
 * User: LRZ
 * Date: 2020/2/28
 * Time: 16:38
 */

/**
 *  38.外观数列
 *
 *  标签：字符串
 *
 *  「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。前五项如下：
 *      1.     1
 *      2.     11
 *      3.     21
 *      4.     1211
 *      5.     111221
 *          1 被读作  "one 1"  ("一个一") , 即 11。
 *          11 被读作 "two 1s" ("两个一"）, 即 21。
 *          21 被读作 "one 2",  "one 1" （"一个二" ,  "一个一") , 即 1211。
 *  给定一个正整数 n（1 ≤ n ≤ 30），输出外观数列的第 n 项。
 *  注意：整数序列中的每一项将表示为一个字符串。
 *
 *  示例 1:
 *      输入: 1
 *      输出: "1"
 *      解释：这是一个基本样例。
 *
 *  示例 2:
 *      输入: 4
 *      输出: "1211"
 *      解释：当 n = 3 时，序列是 "21"，其中我们有 "2" 和 "1" 两组，"2" 可以读作 "12"，也就是出现频次 = 1 而 值 = 2；类似 "1" 可以读作 "11"。所以答案是 "12" 和 "11" 组合在一起，也就是 "1211"。
 *
 *  来源：力扣（LeetCode）
 *  链接：https://leetcode-cn.com/problems/count-and-say
 *  著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

$start = microtime(true);

$n   = 6;
$res = countAndSay($n);

$end = microtime(true);
print_r($res);
printf(' total run: %.2f s<br>' . 'memory usage: %.2f M<br> ', $end - $start, memory_get_usage() / 1024 / 1024);

function countAndSay($n)
{
    $i = 1; # 层级
    $s = '1'; # 第一项

    while ($i < $n) {
        $tmp = '';
        $num = 1; # 元素系数
        for ($j = 1, $sLength = strlen($s); $j < $sLength; $j++) {
            # 相邻的元素相等时，元素系数+1
            if ($s[$j - 1] === $s[$j]) {
                $num++;
            } else { # 连续元素结束，保存当前结果
                $tmp .= $num;
                $tmp .= $s[$j - 1];
                $num = 1; # 重置元素系数
            }
        }
        # 保存出现在末尾的连续元素的结果
        $tmp .= $num;
        $tmp .= $s[$sLength - 1];
        $s   = $tmp;
        $i++;
    }

    return $s;
}